package com.tangyuan.leetcode;

/**
 * @CLASSNAME:
 * @AUTHOR: fenghongyu
 * @TIME: 2021/1/4 20:06
 * 翻转链表前N个数
 * 1->2->3->4->5->NULL
 * 翻转前3个数，变成
 * 3->2->1->4->5->NULL
 */
public class A005ReversN {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        A005ReversN reversN = new A005ReversN();
        reversN.test();
    }

    public void test() {
        ListNode five = new ListNode(5, null);
        ListNode four = new ListNode(4, five);
        ListNode three = new ListNode(3, four);
        ListNode two = new ListNode(2, three);
        ListNode one = new ListNode(1, two);

        printNode(one);

        //测试翻转全链表
//        ListNode result1 = reverseList_2(one);
//        printNode(result1);
        //翻转前N个节点
        ListNode result = reversN(one, 3);
        printNode(result);

    }

    ListNode successor = null; // 后驱节点

    // 反转以 head 为起点的 n 个节点，返回新的头结点：教程答案
    ////1->2->3->4->5->NULL
//    ListNode reverseN(ListNode head, int n) {
//        if (n == 1) {
//            // 记录第 n + 1 个节点
//            successor = head.next;
//            return head;
//        }
//        // 以 head.next 为起点，需要反转前 n - 1 个节点
//        ListNode last = reverseN(head.next, n - 1);
//        //反转当前节点的next指向当前节点,比如3->2
//        head.next.next = head;
//        // 让反转之后的 head 节点和后面的节点连起来
//        head.next = successor;
//        return last;
//    }

    //我的答案
    //1->2->3->4->5->NULL

    ListNode lastNext = null;
    private ListNode reversN(ListNode head, int n) {
        //终止条件
        if (n == 1) {
            lastNext = head.next;
            return head;
        }

        ListNode last = reversN(head.next, n - 1);
        head.next.next = head;
        head.next = lastNext;
        return last;

    }

    // * 输入: 1->2->3->4->5->NULL
    // * 输出: 5->4->3->2->1->NULL
    //递归解决
    public ListNode reverseList_2(ListNode head) {
        //终止条件
        if (head == null || head.next == null) {
            return head;
        }
        //处理当前层逻辑
        //下探到下一层
        ListNode last = reverseList_2(head.next);
        //清理当前层
        head.next.next = head;
        head.next = null;
        return last;
    }


    private static void printNode(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            head = head.next;
        }
        System.out.println("--------");
    }
}
